Có hướng

—Nếu G là đồ thị có hướng không có khuyên, ma trận liên thuộc (hay liên kết đỉnh cạnh) của đồ thị G, ký hiệu A(G), là ma trận n*m (n: số đỉnh, m: số cạnh) được định nghĩa là A = (Aij) với quy ước:

    * Aij = 1 nếu cạnh j hướng ra khỏi đỉnh i     * Aij = -1 nếu cạnh j hướng vào đỉnh i.     * Aij = 0 nếu cạnh j không kề đỉnh i.

Vô hướng

—Nếu G là đồ thị vô hướng không có khuyên, ma trận liên thuộc (hay liên kết đỉnh cạnh) của đồ thị G, ký hiệu A(G), là ma trận n*m (n: số đỉnh, m: số cạnh) được định nghĩa là A = (Aij) với quy ước:

    * Aij = 1 nếu đỉnh i kề với cạnh j.     * Aij = 0 nếu ngược lại.